package no25;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/15 9:41
 * 合并两个有序链表
 * https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/submissions/
 */
public class Solution {
    // 方法一: 带头节点
    public ListNode mergeTwoLists01(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1); // 辅助头节点, 最终头指针为 head.next
        ListNode curL1 = l1; // 用于遍历l1
        ListNode curL2 = l2; // 用于遍历l2
        ListNode cur = head; // 用于构建链表
        // 排序链表的合并
        while(curL1 != null && curL2 != null) {
            if (curL1.val <= curL2.val) {
                cur.next = curL1;
                curL1 = curL1.next;
            } else {
                cur.next = curL2;
                curL2 = curL2.next;
            }
            cur = cur.next;
        }
        // 合并剩余的
        if (curL1 != null) {
            cur.next = curL1;
        } else {
            cur.next = curL2;
        }
        // 返回头指针
        return head.next;
    }

    // 方法二: 不带头节点(推荐)
    public ListNode mergeTwoLists02(ListNode l1, ListNode l2) {
        // 边界处理
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        // 定义合并链表的头尾指针
        ListNode head = null;
        ListNode end = null;
        // 合并过程
        while (l1 != null && l2 != null) {
            // 选择需要删除的节点, 暂时保存, 便于拼接到新链表
            ListNode curNode = l1.val > l2.val ? l2 : l1;
            // 删除目标节点
            if (curNode == l1) {
                l1 = l1.next;
            } else {
                l2 = l2.next;
            }
            // 拼接过程
            if (head == null) {
                // 如果是第一个节点, 则先初始化头指针和尾指针
                head = curNode;
                end = curNode;
            } else {
                // 插入节点 curNode 到新链表
                end.next = curNode;
                end = end.next;
            }
        }
        // 处理两个链表剩余的
        if (l1 == null) {
            end.next = l2;
        } else {
            end.next = l1;
        }
        return head;
    }

    // 方法三: 递归
    public ListNode mergeTwoLists03(ListNode l1, ListNode l2) {
        // 边界处理
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        // 找到合适的节点由 head 指向, 并从原来链表删除
        ListNode head = null;
        if (l1.val > l2.val) {
            head = l2;
            l2 = l2.next;
        } else {
            head = l1;
            l1 = l1.next;
        }
        // 递归处理剩下的
        head.next = mergeTwoLists03(l1, l2);
        return head;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x;}
    }
}
